package com.bichengcao.googlecodejam.round1a2008;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;

public class Numbers {

	static int N;

	public static void main(String[] args) throws IOException {
		Input[] inputs = parseInput("src/com/bichengcao/googlecodejam/round1a2008/C-large-practice.in");
		Output[] outputs = process(inputs);
		writeOutput("src/com/bichengcao/googlecodejam/round1a2008/Numbers.out", outputs);
	}

	static class Input {

		int n;
	}

	static class Output {

		String result;
	}

	private static Input[] parseInput(String filename) throws IOException {
		BufferedReader in = new BufferedReader(new FileReader(filename));
		N = Integer.parseInt(in.readLine());
		Input[] array = new Input[N];

		for (int i = 0; i < N; i++) {
			Input input = array[i] = new Input();
			input.n = Integer.parseInt(in.readLine());
		}

		in.close();
		return array;
	}

	private static int[][][] matrix = new int[31][][];
	
	private static Output[] process(Input[] inputs) {
		Output[] outputs = new Output[N];
		matrix[0] = new int[][] { { 3, 5 }, { 1, 3 } };
		for (int i = 1; i < 31; i++) {
			matrix[i] = MatrixMultiply(matrix[i-1], matrix[i-1]);
		}
		for (int i = 0; i < N; i++) {
			outputs[i] = process(inputs[i]);
		}
		return outputs;
	}

	private static Output process(Input input) {
		Output output = new Output();

		int[] vector = {1, 0};
		for (int i = 0; i < 31; i++) {
			if ((input.n & (1 << i)) != 0) {
				int a = (matrix[i][0][0] * vector[0] + matrix[i][0][1] * vector[1]) % 1000;
				int b = (matrix[i][1][0] * vector[0] + matrix[i][1][1] * vector[1]) % 1000;
				vector[0] = a;
				vector[1] = b;
			}
		}
		int result = (2 * vector[0] + 999) % 1000;
		
		output.result = "" + (result / 100) + (result / 10 % 10) + (result % 10);

		return output;
	}

	private static int[][] MatrixMultiply(int[][] a, int[][] b) {
		int[][] result = new int[2][2];
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < 2; j++) {
				for (int k = 0; k < 2; k++) {
					result[i][j] += a[i][k] * b[k][j];
				}
				result[i][j] = result[i][j] % 1000;
			}
		}
		return result;
	}

	private static void writeOutput(String filename, Output[] outputs) throws IOException {
		PrintWriter out = new PrintWriter(new FileWriter(filename));
		for (int i = 0; i < N; i++) {
			out.println("Case #" + (i + 1) + ": " + outputs[i].result);
		}
		out.close();
	}

}
